#pragma once
void quick_sort(int* data, int ns)
{
	int end;
	int left;
	int right;
	int temp;
	int mid_val;
	end = ns - 1;
	left = 0;
	right = end;
	mid_val = data[end / 2];
	while (left <= right)
	{
		while (data[left] < mid_val)
			left++;
		while (data[right] > mid_val)
			right--;
		if (left < right)
		{
			temp = data[left];
			data[left] = data[right];
			data[right] = temp;
			left++;
			right--;
		}
		else if (left == right)
		{
			left++;
			right--;
		}
	}
	if (left < end)
		quick_sort(data + left, end - left + 1);
	if (right > 0)
		quick_sort(data, right + 1);
}

int purtition(int* dat, int low, int high)
{
	int pivot = dat[low];
	while (low < high)
	{
		while (low < high && dat[high] >= pivot)
			high--;
		dat[low] = dat[high];
		while (low < high && dat[low <= pivot])
			low++;
		dat[high] = dat[low];
	}
	dat[low] = pivot;
	return low;
}
void quick_s(int* dat, int low, int high)
{
	int mid;
	if (low >= high)
		return;
	mid = purtition(dat, low, high);
	quick_s(dat, low, mid - 1);
	quick_s(dat, mid + 1, high);
}
void quick_sort2(int* dat, int ns)
{
	quick_s(dat, 0, ns - 1);
}
